package ch2.link.single;

class LinkNode<E> {     // 单链表结点泛型类
    E data;             // 结点的数据域
    LinkNode<E> next;   // 后继结点的指针域

    public LinkNode() { //构造方法
        next = null;
    }

    public LinkNode(E d) {  //重载构造方法
        this.data = d;
        this.next = null;
    }
}

// 单链表泛型类
public class LinkListClass<E> {         // 链表泛型类
    LinkNode<E> head;                   // 存放头结点
    public LinkListClass() {            // 构造方法
        this.head = new LinkNode<E>();  // 创建头结点
        this.head.next = null;
    }

    private LinkNode<E> geti(int i) {   // 返回序号为i的结点
        LinkNode<E> p = head;
        int j = -1;
        while (j < i) {
            j++;
            p = p.next;
        }
        return p;
        //for (int k = 0; k < i+1; k++) {
        //    p = p.next;
        //}
        //return p;
    }

    //线性表的基本运算算法
    public void CreateListF(E[] a) {    //头插法：由数组a整体建立单链表
        for (int i = 0; i < a.length; i++) {    //循环建立结点s
            LinkNode<E> s = new LinkNode<E>(a[i]);  // 新建存放a[i]元素的结点s
            s.next = head.next;         // 将s结点插入到开始结点之前、头结点之后
            head.next = s;
        }
    }
    public void CreateListR(E[] a) {    // 尾插法：由数组a整体建立单链表
        LinkNode<E> s, t = head;        // t始终指向尾结点,开始时指向头结点
        for (int i = 0; i < a.length; i++) {    // 循环建立结点s
            s = new LinkNode<E>(a[i]);  // 新建存放a[i]元素的结点s
            t.next = s; //将s结点插入t结点之后
            t = s;
        }
        t.next = null;  //将尾结点的next字段置为null
    }

    public void Add(E e) {  //在线性表的末尾添加一个值为e的结点
        LinkNode<E> s = new LinkNode<E>(e); //新建结点s
        LinkNode<E> p = head;
        while (p.next != null) {    //查找尾结点p
            p = p.next;
        }
        p.next = s;     //在尾结点之后插入结点s
    }
    public int size() {     //求链表的长度
        LinkNode<E> p = head;
        int cnt = 0;
        while (p.next != null) {    //找到尾结点为止
            cnt++;
            p = p.next;
        }
        return cnt;
    }

    public void Setsize(int nlen) {     //设置线性表的长度
        int len = size();
        if (nlen < 0 || nlen > len) {
            throw new IllegalArgumentException("设置长度:n不在有效范围内");
        }
        if (nlen == len) {
            return;
        }
        LinkNode<E> p = geti(nlen - 1); //找到序号为nlen-1的结点p
        p.next = null;  //将结点p置为尾结点
    }

    public E GetElem(int i) {   //返回链表中序号为i的结点的值
        int len = size();
        if (i < 0 || i > len - 1) {
            throw new IllegalArgumentException("查找:位置i不在有效范围内");
        }
        LinkNode<E> p = geti(i);    //找到序号为i的结点p
        return (E) p.data;
    }

    public void SetElem(int i, E e) {   //设置序号i结点的元素值为e
        if (i < 0 || i > size() - 1) {
            throw new IllegalArgumentException("设置:位置i不在有效范围内");
        }
        LinkNode<E> p = geti(i);    //找到序号为i的结点p
        p.data = e;
    }

    public int GetNo(E e) { //查找第一个元素值为e的结点的序号
        int j = 0;
        LinkNode<E> p = head.next;
        while (p != null && !p.data.equals(e)) {
            j++;    //记录元素值不为e的结点序号
            p = p.next;
        }
        if (p == null) {    //未找到时返回-1
            return -1;
        } else {
            return j;       //找到后返回其序号
        }
    }

    public void swap(int i, int j) {    //交换序号i和序号j的结点的值
        LinkNode<E> p = geti(i);
        LinkNode<E> q = geti(j);
        E tmp = p.data;
        p.data = q.data;
        q.data = tmp;
    }

    public void Insert(int i, E e) {    //在链表中的序号i插入值为e的结点
        if (i < 0 || i > size()) {      //参数错误抛出异常
            throw new IllegalArgumentException("插入:位置i不在有效范围内");
        }
        LinkNode<E> s = new LinkNode<E>(e);     //建立新结点s
        LinkNode<E> p = geti(i - 1);   //找到序号为i-1的结点p
        s.next = p.next;    //在p结点后面插入s结点
        p.next = s;
    }

    public void Delete(int i) {         //在链表中删除序号i位置的结点
        if (i < 0 || i > size() - 1) {  //参数错误抛出异常
            throw new IllegalArgumentException("删除:位置i不在有效范围内");
        }
        LinkNode<E> p = geti(i - 1);    //找到序号为i-1的结点p
        p.next = p.next.next;             //删除p结点的后继结点
    }

    @Override
    public String toString() {  //将链表转换为字符串
        String ans = "";
        LinkNode<E> p = head.next;
        while (p != null) {
            ans += p.data + " ";
            p = p.next;
        }
        return ans;
    }

    public static void main(String[] args) {
        //测试1：数据为整型
        System.out.println("****************测试1****************");
        Integer[] a = {1, 2, 3, 4, 5};
        LinkListClass<Integer> L1 = new LinkListClass<>();

        // 1. 尾插法创建链表
        L1.CreateListR(a);
        System.out.println("L1: " + L1);
        System.out.println("L1长度=" + L1.size());

        // 2.在末尾添加结点
        L1.Add(10);
        System.out.println("L1: " + L1);

        // 遍历每个结点，调用GetElem()输出结点值
        System.out.println("求每个序号的结点值");
        for (int i = 0; i < L1.size(); i++) {
            System.out.println("  序号" + i + "的结点值:" + L1.GetElem(i));
        }

        // 重置长度
        System.out.println("重新置长度为5");
        L1.Setsize(5);
        System.out.println("L1: " + L1);

        // 在指定位置插入结点
        int i = 1;
        Integer x = 20;
        System.out.println("在序号" + i + "位置插入" + x);
        L1.Insert(i, x);
        System.out.println("L1: " + L1);

        // 删除指定位置的结点
        i = 3;
        System.out.println("删除序号" + i + "的结点");
        L1.Delete(i);
        System.out.println("L1: " + L1);

        // 替换指定位置的结点的值
        i = 2;
        x = 16;
        System.out.println("设置序号" + i + "的结点值为" + x);
        L1.SetElem(i, x);
        System.out.println("L1: " + L1);

        // 获取值为5的结点的序号
        x = 5;
        System.out.println("值为" + x + "的结点序号为" + L1.GetNo(x));

        // 测试2：数据为字符
        System.out.println();
        System.out.println("****************测试2****************");
        Character[] b = {'a', 'b', 'c', 'd', 'e', 'f'};
        LinkListClass<Character> L2 = new LinkListClass<>();

        L2.CreateListR(b);
        System.out.println("L2: " + L2);
        System.out.println("L2长度=" + L2.size());

        L2.Add('x');
        System.out.println("L2: " + L2);

        System.out.println("求每个序号的结点值");
        for (i = 0; i < L2.size(); i++) {
            System.out.println("  序号" + i + "的结点值:" + L2.GetElem(i));
        }

        System.out.println("重新置长度为5");
        L2.Setsize(5);
        System.out.println("L2: " + L2);

        i = 1;
        Character y = 'y';
        System.out.println("在序号" + i + "位置插入" + y);
        L2.Insert(i, y);
        System.out.println("L2: " + L2);

        i = 3;
        System.out.println("删除序号" + i + "的结点");
        L2.Delete(i);
        System.out.println("L2: " + L2);

        i = 2;
        y = 'z';
        System.out.println("设置序号" + i + "的结点值为" + y);
        L2.SetElem(i, y);
        System.out.println("L2: " + L2);

        y = 'd';
        System.out.println("值为" + y + "的结点序号为" + L2.GetNo(y));

        // 测试3：数据为字符串，头插法创建单链表
        System.out.println();
        System.out.println("****************测试3****************");
        String c = "abcdef";
        LinkListClass<Character> L3 = new LinkListClass<>();
        L3.CreateListF(c.chars()            // IntStream，也可使用c.codePoints()
                .mapToObj(ch ->(char)ch)    // Stream<Character>
                .toArray(Character[]::new));
        System.out.println("L3: " + L3);
    }
}
